package com.xyhuo.leetcode.january;

import java.util.*;

/**
 * 复原IP地址
 * https://leetcode.cn/problems/restore-ip-addresses/description/
 *
 * @time 2024/1/3
 */
public class RestoreIpAddresses {

//    public static void main(String[] args) {
//        RestoreIpAddresses ria = new RestoreIpAddresses();
//        ria.restoreIpAddresses("101023");
//    }

    public List<String> restoreIpAddresses(String s) {
        Deque<String> deque = new ArrayDeque<>();
        search(s, 0, deque);
        for (int i = 0; i < ans.size(); i++) {
            System.out.println(ans.get(i));
        }
        return ans;
    }

    private List<String> ans = new ArrayList<>();

    private void search(String s, int index, Deque<String> deque) {
        if (deque.size() == 4) {
            if (index >= s.length()) {
                StringBuilder sb = new StringBuilder();
                Iterator<String> iterator = deque.iterator();
                while (iterator.hasNext()) {
                    sb.append(iterator.next());
                    sb.append(".");
                }
                ans.add(sb.substring(0, sb.length() - 1).toString());
            }
            return;
        }
        if (index >= s.length()) {
            return;
        }
        String one = s.substring(index, index + 1);
        deque.addLast(one);
        search(s, index + 1, deque);
        deque.removeLast();
        if (!one.equals("0")) {
            if (index + 1 < s.length()) {
                String two = s.substring(index, index + 2);
                deque.addLast(two);
                search(s, index + 2, deque);
                deque.removeLast();
            }
            if (index + 2 < s.length()) {
                String three = s.substring(index, index + 3);
                int threeI = Integer.parseInt(three);
                if (threeI <= 255) {
                    deque.addLast(three);
                    search(s, index + 3, deque);
                    deque.removeLast();
                }
            }
        }


    }
}
